package LearnDataStructure.c_树结构.有序树;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 15:05
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.有序树
 */

import LearnDataStructure.c_树结构.TrieNode;
import sun.text.normalizer.Trie;

/**
 * 英文单词前缀树
 * 多分枝树，可以认为是26叉树
 */
public class MyTrie {
    TrieNode root = null;

    public MyTrie(TrieNode root) {
        this.root = new TrieNode();
    }

    /**
     * 添加一个词语
     * @param str
     */
    public void insert(String str) {
        char[] chars = str.toCharArray();//转成字符数组
        TrieNode p = root;
        for (int i = 0; i < chars.length; i++) {//对每一个字符element进行操作
            char element = chars[i];
            TrieNode targetChild = p.children[element - 'a'];//获得element在p的孩子坑的位置
            if (targetChild == null) {//如果坑是空
                TrieNode realityChild = new TrieNode();//产生实际将要放进坑中的孩子
                realityChild.level = i;//设置层数
                realityChild.parent = p;
                p.children[element - 'a'] = realityChild;///放入孩子
                p = realityChild;//指针下移；无需对孩子的频率进行操作，因为频率默认为1
            } else {//坑被填了
                p = targetChild;//指针下移
                targetChild.frequency++;//频率加一
            }
        }
        //在跳出循环后，p一定指向最后一个element所在的层级，也就是最后一个字符的位置
        p.isLast = true;//把这个字符设置成结束字符，即代表着str完全放入了Trie
    }

    /**
     * 打印全树中的词语
     */
    public void printAll() {
        print("", root);
    }

    /**
     * @param prefix 当前已经拼好的前缀
     * @param node 当前给前缀添加新字符，新字符从哪里来？从node来
     */
    private void print(String prefix, TrieNode node) {
        if (node.isLast && prefix.length() > 0) {//递归出口，末尾单词
            System.out.println("word: " + prefix + " ; frequency: " + node.frequency);
            return;
        }
        for (int i = 0; i < 26; i++) {//递归分叉，26叉
            if (node.children[i] != null) {
                print((prefix + (char)('a' + i)), node.children[i]);
            }
        }
    }

    /**
     * 给定前缀，返回所有这个前缀的词语
     * @param prefix
     */
    public void search(String prefix) {
        char[] chars = prefix.toCharArray();
        TrieNode p = root;
        for (int i = 0; i < chars.length; i++) {
            char element = chars[i];
            TrieNode targetChild = p.children[element - 'a'];
            if (targetChild == null) {//如果搜索过程中，遇到了一次，坑没有被填
                return;//就代表这个前缀，没有在树中存在，所以直接返回空代表没搜到
            } else {
                p = targetChild;
            }
        }
        print(prefix, p);//递归的返回所有这个前缀的词语
    }
}
